#ifndef DFS_H
#define DFS_H

#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/dynamic_bitset.hpp>

struct points_to_t{
	typedef boost::vertex_property_tag kind;
};
struct load_from_t{
	typedef boost::vertex_property_tag kind;
};
struct store_to_t{
	typedef boost::vertex_property_tag kind;
};

struct component_index_t{
	typedef boost::vertex_property_tag kind;
};

typedef boost::property<points_to_t, boost::dynamic_bitset<unsigned int> > points_to;	//points_to[i]: set of variables which i points to
typedef boost::property<load_from_t, boost::dynamic_bitset<unsigned int>, points_to> load_from;	//load_from[i]: set of variables j such that j = *i
typedef boost::property<store_to_t, boost::dynamic_bitset<unsigned int>, load_from> store_to;	//store_to[i]: set of variables j such that *i = j
typedef boost::property<component_index_t, unsigned int, store_to> component_index;
typedef boost::property<boost::vertex_index_t, int, component_index> vertex_info;

typedef boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, vertex_info> Graph;
typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter;
typedef std::pair<vertex_iter, vertex_iter> vertices_range;
typedef boost::graph_traits<Graph>::edge_iterator edge_iter;
typedef std::pair<edge_iter, edge_iter> edges_range;
typedef boost::graph_traits<Graph>::adjacency_iterator adj_iter;
typedef std::pair<adj_iter, adj_iter> adj_vertices_range;

typedef boost::graph_traits<Graph>::out_edge_iterator out_edge_iter;
typedef std::pair<out_edge_iter, out_edge_iter> out_edge_range;
typedef boost::graph_traits<Graph>::in_edge_iterator in_edge_iter;
typedef std::pair<in_edge_iter, in_edge_iter> in_edge_range;

typedef boost::property_map<Graph, boost::vertex_index_t>::type index_map;
typedef boost::property_map<Graph, component_index_t>::type component_map;
typedef boost::property_map<Graph, store_to_t>::type store_to_map;
typedef boost::property_map<Graph, load_from_t>::type load_from_map;
typedef boost::property_map<Graph, points_to_t>::type points_to_map;

typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_search_result;

typedef std::priority_queue<int> work_list;

typedef boost::graph_traits<Graph>::edge_descriptor Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

typedef boost::graph_traits<Graph>::vertices_size_type size_type;

struct dfs_path_recorder : public boost::default_dfs_visitor{
	static std::map<Vertex, Vertex> predecessor;
	dfs_path_recorder();
	void tree_edge(Edge e, const Graph &g);
};

#endif
